#define  _CRT_SECURE_NO_WARNINGS 1


//#include <stdbool.h>
//#include <stdio.h>
//int main()
//{
//    int n = 0;
//    int b = 0, c = 0;
//    scanf("%d", &n);
//    int i = 0;
//    int a[50];
//    for (i = 0; i < n; i++)
//        scanf("%d", &a[i]);
//    for (i = 0; i < n - 1; i++)
//    {
//        if (a[i] >= a[i + 1])
//            c++;
//        if (a[i] <= a[i + 1])
//            b++;
//    }
//    if (c + 1 == n || b + 1 == n)
//        printf("sorted\n");
//    else
//        printf("unsorted\n");
//    return 0;
//}

//#include <stdio.h>
//int main()
//{
//    int n = 0;
//    scanf("%d", &n);
//    int i = 0;
//    int sum = 0, m = 0;
//    for (i = 0; i < n; i++)
//    {
//        scanf("%d", &m);
//        sum += m;
//    }
//    printf("%d", sum);
//    return 0;
//}

//#include <stdio.h>
//int main()
//{
//    int n = 0;
//    int a[10];
//    for (n = 0; n < 10; n++)
//    {
//        scanf("%d", &a[n]);
//    }
//    for (n = 0; n < 5; n++)
//    {
//        int tmp = a[n];
//        a[n] = a[9 - n];
//        a[9 - n] = tmp;
//    }
//    for (n = 0; n < 10; n++)
//        printf("%d ", a[n]);
//    return 0;
//}

//#include <math.h>
//#include <stdio.h>
//int main()
//{
//    int m, n;
//    scanf("%d %d", &m, &n);
//    int i = 0, j = 0; int sum = 0;
//    int a[10][10] = { 0 };
//    for (i = 0; i < m; i++)
//    {
//        for (j = 0; j < n; j++)
//        {
//            scanf("%d ", &a[i][j]);
//            if (a[i][j] > 0)
//            {
//                sum += a[i][j];
//            }
//        }
//    }
//    printf("%d", sum);
//    return 0;
//}

//#include <math.h>
//#include <stdio.h>
//int main()
//{
//    int m, n;
//    scanf("%d %d", &m, &n);
//    int i = 0, j = 0; int sum = 0;
//    int a[10][10] = { 0 };
//    for (i = 0; i < m; i++)
//    {
//        for (j = 0; j < n; j++)
//        {
//            scanf("%d ", &a[i][j]);
//        }
//    }
//    for (i = 0; i < m; i++)
//    {
//        for (j = 0; j < n; j++)
//        {
//            if (a[i][j] > 0)
//            {
//                sum += a[i][j];
//            }
//        }
//    }
//    printf("%d", sum);
//    return 0;
//}

//#include <stdio.h>
//#include <string.h>
//int main()
//{
//    char a[100], b[100];
//    while (scanf("%s %s", a, b) != EOF)
//    {
//        int i = 0;
//        if (strcmp(a, b) == 0)
//        {
//            printf("same\n");
//        }
//        else
//        {
//            printf("different\n");
//        }
//    }
//    return 0;
//}

//#include <stdio.h>
//int main()
//{
//    int n = 0;
//    scanf("%d", &n);
//    int i = 0;
//    double a[100];
//    double sum = 0, max = 0.0, min = 100.0;
//    for (i = 0; i < n; i++)
//    {
//        scanf("%lf", &a[i]);
//        sum += a[i];
//        if (max < a[i])
//            max = a[i];
//        if (min > a[i])
//            min = a[i];
//    }
//    printf("%.2lf %.2lf %.2lf", max, min, sum / n);
//    return 0;
//}

//#include <stdio.h>
//int main()
//{
//    int n = 0;
//    scanf("%d", &n);
//    int i = 0;
//    double a[100];
//    double sum = 0, max = 0.0, min = 100.0;
//    for (i = 0; i < n; i++)
//    {
//        scanf("%lf", &a[i]);
//        sum += a[i];
//    }
//    for (i = 0; i < n; i++)
//    {
//        if (max < a[i])
//            max = a[i];
//        if (min > a[i])
//            min = a[i];
//    }
//    printf("%.2lf %.2lf %.2lf", max, min, sum / n);
//    return 0;
//}

//#include <math.h>
//#include <stdio.h>
//int main()
//{
//    int n = 0;
//    int a = 0, b = 0;
//    scanf("%d", &n);
//    int i = 0;
//    for (i = 1; i <= n; i++)
//    {
//        if (i % 2 == 0)
//            a++;
//        else
//            b++;
//    }
//    printf("%d %d", b, a);
//    return 0;
//}

//#include <stdio.h>
//int main()
//{
//    int i = 0; int s = 0;
//    for (; i <= 2019; i++)
//    {
//        int m = i % 10;
//        int n = i / 10 % 10;
//        int k = i / 100 % 10;
//        int l = i / 1000;
//        if (m == 9 || n == 9 || k == 9 || l == 9)
//        {
//            s++;
//        }
//    }
//    printf("%d ", s);
//    return 0;
//}

//#include <stdio.h>
//int main()
//{
//    int a, b, c, d;
//    scanf("%d%d%d%d", &a, &b, &c, &d);
//    printf("%d", (a + b - c) * d);
//    return 0;
//}

//#include <stdio.h>
//#include <string.h>
//int main()
//{
//    char a[100], b[100];
//    while (scanf("%s %s", a, b) != EOF)
//    {
//        int i = 0;
//        if (strcmp(a, b) == 0)
//        {
//            printf("Login Success!\n");
//        }
//        else
//        {
//            printf("Login Fail!\n");
//        }
//    }
//    return 0;
//}

//#include <stdio.h>
//int main()
//{
//    int m, n;
//    scanf("%d%d", &m, &n);
//    int a[100][100], b[100][100];
//    int i = 0; double k = 0.0;
//    for (i = 0; i < m; i++)
//    {
//        int j = 0;
//        for (j = 0; j < n; j++)
//        {
//            scanf("%d", &a[i][j]);
//        }
//    }
//    for (i = 0; i < m; i++)
//    {
//        int j = 0;
//        for (j = 0; j < n; j++)
//        {
//            scanf("%d", &b[i][j]);
//        }
//    }
//    for (i = 0; i < m; i++)
//    {
//        int j = 0;
//        for (j = 0; j < n; j++)
//        {
//            if (a[i][j] == b[i][j])
//            {
//                k++;
//            }
//        }
//    }
//    printf("%.2lf", (double)(k / (m * n) * 100));
//    return 0;
//}

//#include <math.h>
//#include <stdio.h>
//int main()
//{
//    int n = 0;
//    while ((scanf("%d", &n)) != EOF)
//    {
//        int a = 0;
//        int i = 0;
//        for (i = 2; i <= n; i++)
//        {
//            int j = 0;
//            for (j = 2; j < i; j++)
//            {
//                if (i % j == 0)
//                    break;
//            }
//            if (i == j)
//            {
//                printf("%d ", i);
//                a++;
//            }
//        }
//        printf("\n%d", n - a - 1);
//    }
//    return 0;
//}

//#include <stdio.h>
//int main()
//{
//    int n = 0;
//    scanf("%d", &n);
//    int i = 0;
//    int a[50] = { 0 };
//    for (i = 0; i < n; i++)
//    {
//        scanf("%d ", &a[i]);
//    }
//    scanf("%d", &a[n]);
//    for (i = 0; i < n; i++)
//    {
//        int j = 0;
//        for (j = 0; j < n - i; j++)
//        {
//            if (a[j] > a[j + 1])
//            {
//                int tmp = a[j];
//                a[j] = a[j + 1];
//                a[j + 1] = tmp;
//            }
//        }
//    }
//    for (i = 0; i < n + 1; i++)
//    {
//        printf("%d ", a[i]);
//    }
//    return 0;
//}